package com.lun.swordtowardoffer2.c05;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

public class RandomizedSet {
	private HashMap<Integer, Integer> num2Location;
	private ArrayList<Integer> nums;
	
	public RandomizedSet() {
		num2Location = new HashMap<>();
		nums = new ArrayList<>();
	}
	
	public boolean insert(int val) {
		if(num2Location.containsKey(val)) {
			return false;
		}
		
		num2Location.put(val, nums.size());
		nums.add(val);
		
		return true;
	}
	
	public boolean remove(int val) {
		if(!num2Location.containsKey(val)) {
			return false; 
		}
		
		int index = num2Location.get(val);
		num2Location.put(nums.get(nums.size() - 1), index);//拿数组中最后一个元素补空缺位置
		num2Location.remove(val);
		
		//把数组的最后一个，填补要删的
		nums.set(index, nums.get(nums.size() - 1));
		nums.remove(nums.size() - 1);//移除最后一个位置
		return true;
	}
	
	
	public int getValue() {
		Random rand = new Random();
		return nums.get(rand.nextInt(nums.size()));
	}
	
}
